package algorithm.niuke;

import java.util.*;

class Solution {
    List<List<Integer>> result = new ArrayList<>();
    boolean log = true;

    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<Integer> list = new ArrayList<>();
        for (int num : nums) {
            list.add(num);
        }
        Collections.sort(list);
        Integer[] pre = new Integer[4];
        dfs_n_sum(1, 4, target, list, 0, pre);
        return result;
    }

    boolean dfs_n_sum(int n, int total, int target, List<Integer> list, int start, Integer[] pre) {
        if (start >= list.size()) {
            return false;
        }
        if (n == total) {
            if (list.contains(target) && list.get(start) <= target) {
                pre[n - 1] = target;
                result.add(Arrays.asList(Arrays.copyOf(pre, pre.length)));
            }
            return true;
        }
        int index = start;
        while (index < list.size()) {
            if (index == start || list.get(index) > list.get(index - 1)) {
                pre[n-1] = list.get(index);
                if (log) {
                    System.out.println(n + " " + list.get(index));
                }
                int tempTarget = target - list.get(index);
                if (tempTarget < (total - n) * (list.get(index))) {
                    break;
                }
                boolean goOn = dfs_n_sum(n + 1, total, tempTarget, list, index + 1, pre);
                if (!goOn) {
                    break;
                }
            }
            index++;
        }
        return true;
    }

    public static void main(String[] args) {
        Solution run = new Solution();
        int[] nums = { 1, 0, -1, 0, -2, 2 };
        run.fourSum(nums, 0);
    }
}